package priv.sort.bucket;

import java.util.ArrayList;
import java.util.List;

public class BucketSort {
    // bucket 的大小
    private static final int BUCKET_SIZE = 20;

    // 为了统一调用才使用 int[] arr，建议换成 List
    public static void sort(int[] arr) {
        if (arr.length < 2) return;
        List<Integer> list = new ArrayList<>();
        for (int value : arr) {
            list.add(value);
        }
        list = sort(list, BUCKET_SIZE);
        for (int i = 0; i < arr.length; i++) {
            arr[i] = list.get(i);
        }
    }

    private static List<Integer> sort(List<Integer> list, int bucketSize) {
        if (list.size() < 2 || bucketSize == 0) {
            return list;
        }
        int min = list.get(0), max = list.get(0);
        for (Integer integer : list) {
            if (integer < min) {
                min = integer;
            } else if (integer > max) {
                max = integer;
            }
        }
        // 计算 bucket 的数量
        int bucketCount = (max - min) / bucketSize + 1;
        List<List<Integer>> buckets = new ArrayList<>();
        for (int i = 0; i < bucketCount; i++) {
            buckets.add(new ArrayList<>());
        }
        // 将元素放入 bucket 中
        for (Integer integer : list) {
            int index = (integer - min) / bucketSize;
            buckets.get(index).add(integer);
        }
        // 对每个 bucket 进行排序
        for (int i = 0; i < bucketCount; i++) {
            if (!buckets.get(i).isEmpty()) {
                // 此处排序算法可以换成其他排序算法，本项目大部分都使用 int[] 作为参数， 不好更换
                buckets.set(i, sort(buckets.get(i), bucketSize / 2));
            }
        }
        // 将 bucket 中的元素放回原数组
        List<Integer> result = new ArrayList<>();
        for (List<Integer> bucket : buckets) {
            result.addAll(bucket);
        }
        return result;
    }
}
